/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class MaximalRectangle {

	public int getMax(char[][] matrix) {
		int n = matrix.length;
		int m = matrix[0].length;
		int[] a = new int[m];
		int max = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (matrix[i][j] == '1') {
					a[j]++;
				} else {
					a[j] = 0;
				}
			}
			int[] val = new int[m];
			int[] stack = new int[m + 1];
			int top = -1;
			stack[++top] = -1;
			for (int j = 0; j < m; ++j) {
				while (stack[top] >= 0 && a[stack[top]] >= a[j]) {
					top--;
				}
				val[j] += a[j] * (j - stack[top]);
				stack[++top] = j;
			}
			top = -1;
			stack[++top] = m;
			for (int j = m - 1; j >= 0; --j) {
				while (stack[top] < m && a[stack[top]] >= a[j]) {
					top--;
				}
				val[j] += a[j] * (stack[top] - j);
				stack[++top] = j;
			}
			for (int j = 0; j < m; ++j) {
				max = Math.max(max, val[j] - a[j]);
			}
		}
		return max;
	}

	public int maximalRectangle(char[][] matrix) {
		if (matrix.length == 0 || matrix[0].length == 0)
			return 0;
		int n = matrix.length;
		int m = matrix[0].length;
		int max = 0;
		max = getMax(matrix);
		for (int i = 0; i < n / 2; ++i) {
			for (int j = 0; j < m; ++j) {
				char tmp = matrix[i][j];
				matrix[i][j] = matrix[n - 1 - i][j];
				matrix[n - 1 - i][j] = tmp;
			}
		}
		max = Math.max(max, getMax(matrix));
		return max;
	}

	public static void main(String[] args) {
		char[][] m = new char[][] { { '1', '1', '1', '1' },
				{ '1', '1', '1', '1' }, { '1', '1', '1', '1' },
				{ '1', '1', '1', '1' } };
		MaximalRectangle a = new MaximalRectangle();
		System.out.println(a.maximalRectangle(m));
	}

}
